接下來將正式進入資料結構相關的問題，首先是 Linked List．
關於用 Python 實作 Linked List ，我覺得這篇文章寫得非常好，強烈建議大家去看原文，今天就分享一點整理的筆記．

效能比較: List vs Linked List

在 Python 這個程式語言, list 是動態陣列. 這表示在記憶體空間使用上，list 跟 linked lists 是相差無幾的．

然而 list 在插入新的元素時，需要耗費時間在把新插入位置後面的元素全部在背景往後移．當你把新的元素插入到 list 的最前面時，時間複雜度會來到 O(n)

另一方面, Linked List 在插入或移除最前面的元素時就沒有這個問題，他所花的時間複雜度是O(1)．

Linked List 概念

List 使用 連續的記憶體空間 來儲存資料,
Linked List 儲存資料的記憶體是非連續，不需事先知道整體資料大小．它儲存資料的單位稱為node(節點)，每個節點中包含至少下列兩個資料格式:

• Data: 儲存資料值.
• Next: 儲存到下一個節點記憶體位置的 pointer.

實作 Linked List

補充： __repr__ 是用來將一個物件以字串的方式來表示，因此我們可以用 print() 來列出該物件的資料．

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

    def __repr__(self):
        return self.data

class LinkedList:
    def __init__(self):
        self.head = None
    
    def __init__(self, nodes=None):
        self.head = None
        if nodes is not None:
            node = Node(data=nodes.pop(0))
            self.head = node
            for elem in nodes:
                node.next = Node(data=elem)
                node = node.next

    def __repr__(self):
        node = self.head
        nodes = []
        while node is not None:
            nodes.append(node.data)
            node = node.next
        nodes.append("None")
        return " -> ".join(nodes)

走訪(traverse) 所有節點

使用 while 迴圈

llist = LinkedList(["a", "b", "c"])
node = llist.head
while node is not None:
  print(node.data)
  node = node.next

或實作 __iter__() 函式使該 Linked List 物件變成可迭代的（iterable）.

class LinkedList:
    def __init__(self):
        self.head = None

    def __init__(self, nodes=None):
        self.head = None
        if nodes is not None:
            node = Node(data=nodes.pop(0))
            self.head = node
            for elem in nodes:
                node.next = Node(data=elem)
                node = node.next

    def __repr__(self):
        node = self.head
        nodes = []
        while node is not None:
            nodes.append(node.data)
            node = node.next
        nodes.append("None")
        return " -> ".join(nodes)

    def __iter__(self):
        node = self.head
        while node is not None:
            yield node
            node = node.next

補充： yield 可暫停 function 的執行並將值先回傳給呼叫者, function 之後可以稍後繼續重新執行剩下的部分

當物件變成可迭代的時，我們就可以用 for 迴圈來走訪每個節點

for node in llist:
  print(node.data)

Insert 插入新元素

def add_first(self, node):
    node.next = self.head
    self.head = node

def add_last(self, node):
    """
    traverse the whole list until you reach the end
    """
    if self.head is None:
        self.head = node
        return
    current_node = self.head
    while current_node.next is not None:
        current_node = node.next
    current_node.next = node

def add_after(self, target_node_data, new_node):
    if self.head is None:
        raise Exception("List is empty")

    for node in self:
        if node.data == target_node_data:
            new_node.next = node.next
            node.next = new_node
            return

    raise Exception("Node with data '%s' not found" % target_node_data)

移除元素

def remove_node(self, target_node_data):
    if self.head is None:
        raise Exception("List is empty")

    if self.head.data == target_node_data:
        self.head = self.head.next
        return

    previous_node = self.head
    for node in self:
        if node.data == target_node_data:
            previous_node.next = node.next
            return
        previous_node = node

    raise Exception("Node with data '%s' not found" % target_node_data)